package daily.oct;

import java.util.PriorityQueue;

public class lc407 {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;
        if (heightMap == null || m < 3 || n < 3) {//长宽都小于3时，无法接水，直接返回0即可
            return 0;
        }

        boolean[][] visited = new boolean[m][n];//记录是否访问过该点
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);//小根堆，根据高度排序

        //将边界加入小根堆
        for (int i = 0; i < m; i++) {//将第一列和最后一列加入小根堆
            pq.offer(new int[] { heightMap[i][0], i, 0 });
            pq.offer(new int[] { heightMap[i][n - 1], i, n - 1 });
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }
        for (int j = 0; j < n; j++) {//将第一行和最后一行加入小根堆
            pq.offer(new int[] { heightMap[0][j], 0, j });
            pq.offer(new int[] { heightMap[m - 1][j], m - 1, j });
            visited[0][j] = true;
            visited[m - 1][j] = true;
        }

        int ans = 0;
        int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };//方向数组，用于遍历上下左右四个方向
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();//取出当前高度最小的点 (poll:弹出队首元素)
            for (int[] dir : dirs) {//遍历上下左右四个方向
                int x = cur[1] + dir[0];//计算新的坐标
                int y = cur[2] + dir[1];//计算新的坐标
                if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {//如果新的坐标越界或者已经访问过，直接跳过
                    continue;
                }
                ans += Math.max(0, cur[0] - heightMap[x][y]);//如果新的坐标的高度小于当前高度，说明可以接水，计算接水高度并加入ans中
                pq.offer(new int[] { Math.max(heightMap[x][y], cur[0]), x, y });
                //将新的坐标加入小根堆 (Math.max(heightMap[x][y], cur[0]):新的高度为当前高度和新坐标高度的较大值)
                visited[x][y] = true;//标记为已访问
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        lc407 lc407 = new lc407();
        int[][] heightMap1 = { { 1, 4, 3, 1, 3, 2 }, { 3, 2, 1, 3, 2, 4 }, { 2, 3, 3, 2, 3, 1 } };
        int[][] heightMap2 = { { 3, 3, 3, 3, 3 }, { 3, 2, 2, 2, 3 }, { 3, 2, 1, 2, 3 }, { 3, 2, 2, 2, 3 }, { 3, 3, 3, 3, 3 } };
        int ans1 = lc407.trapRainWater(heightMap1);
        int ans2 = lc407.trapRainWater(heightMap2);
        System.out.println(ans1);
        System.out.println(ans2);
    }
    
}
